//
//  37.数字在升序数组中出现的次数.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/24.
//

import Foundation
/*
 题目：统计一个数字在升序数组中出现的次数。
 
 思路1：一次循环O(n)
 思路2：二分法O(logn)
 */
func offer_37() {
    func measure(title: String!, call: () -> Void) {
        let startTime = CFAbsoluteTimeGetCurrent()
        call()
        let endTime = CFAbsoluteTimeGetCurrent()
        if let title = title {
            print("\(title): ")
        }
        print("Time - \(endTime - startTime)")
     }
    
    var arr1 = [Int]()
    var arr2 = [Int]()
    var arr3 = [Int]()
    for i in 0..<20000000 {
        arr1.append(i)
        arr2.append(i)
        arr3.append(i)
    }
    for _ in 0..<200000 {
        arr1.append(20000000)
        arr2.append(20000000)
        arr3.append(20000000)
    }
    for i in 20000000..<30000000 {
        arr1.append(i)
        arr2.append(i)
        arr3.append(i)
    }
    
    measure(title: "方法2") {
        print(Solution().getNumberOfK2(arr2,20000000))
    }
    measure(title: "方法3") {
        print(Solution().getNumberOfK3(arr3,20000000))
    }
    measure(title: "方法1") {
        print(Solution().getNumberOfK1(arr1,20000000))
    }
}

fileprivate class Solution {
    func getNumberOfK1(_ data: [Int], _ k: Int) -> Int {
        guard !data.isEmpty else { return 0 }
        var count = 0
        for num in data {
            if k == num {
                count += 1
            }
        }
        return count
    }
    
    func getNumberOfK2(_ data: [Int], _ k: Int) -> Int {
        guard !data.isEmpty else { return 0 }
        var count = 0
        var left = 0
        var right = data.count
        while left < right {
            let mid = (left + right) >> 1
            if data[mid] > k {
                right = mid
            } else if data[mid] < k {
                left = mid
            } else {
                var temp = mid
                while temp > 0 && data[temp] == k {
                    count += 1
                    temp -= 1
                }
                temp = mid+1
                while temp < data.count && data[temp] == k {
                    count += 1
                    temp += 1
                }
                break
            }
        }
        return count
    }
    
    func getNumberOfK3(_ data: [Int], _ k: Int) -> Int {
        guard !data.isEmpty else { return 0 }
        var left = 0
        var right = data.count
        while left < right {
            let mid = (left + right) >> 1
            if data[mid] < k {
                left = mid+1
            } else {
                right = mid
            }
        }
        let l = left
        
        left = -1
        right = data.count - 1
        while left < right {
            let mid = (left + right + 1) >> 1
            if data[mid] > k {
                right = mid - 1
            } else {
                left = mid
            }
        }
        let r = right + 1
        
        return r - l
    }
}
